using System;
using System.Diagnostics;
using BepuUtilities.Memory;
using System.Collections.Generic;
using System.Runtime.CompilerServices;

namespace BepuUtilities.Collections
{
    /// <summary>
    /// 支持在池化数组上构建的双端队列行为的容器。
    /// </summary>
    /// <remarks>
    /// 使用此类型时要非常小心。它在性能的祭坛上牺牲了很多;几个值得注意的问题包括：
    /// 它是一种值类型,复制它会在不加注意的情况下破坏东西,
    /// 它不能被有效地缺省构造,
    /// 它将内部结构暴露给用户修改,
    /// 它很少检查输入是否有错误,
    /// 枚举器不检查枚举中期修改,
    /// 它允许不安全的添加,如果用户不管理容量可能会中断,
    /// 它在抽象的存储器二进制大对象之上工作,该抽象的存储器二进制大对象在内部可能是可以被拉动的指针,
    /// 它不(也不能)检查所提供的内存是否返回到它来自的同一池。
    /// </remarks>
    /// <typeparam name="T">队列中元素的类型。</typeparam>
    public struct QuickQueue<T> where T : unmanaged
    {
        /// <summary>
        /// 队列中的元素数。
        /// </summary>
        public int Count;

        /// <summary>
        /// 队列中第一个元素的索引。
        /// </summary>
        public int FirstIndex;

        /// <summary>
        /// 队列中最后一个元素的索引。
        /// </summary>
        public int LastIndex;

        /// <summary>
        /// 基于用于执行快速模运算的当前跨度长度的掩码;要求跨度长度的幂为2。
        /// </summary>
        public int CapacityMask;

        /// <summary>
        /// 获取包含队列元素的后备内存。
        /// 从FirstIndex到LastIndex(含)的指数保存实际数据。所有其他数据均未定义。
        /// 注意换行;即使当count>0时,LastIndex也可能小于FirstIndex！
        /// </summary>
        public Buffer<T> Span;

        /// <summary>
        /// 获取逻辑队列索引的后备数组索引。
        /// </summary>
        /// <param name="queue eIndex">逻辑队列中的索引。</param>
        /// <return>与给定逻辑队列索引对应的后备数组中的索引。</return>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int GetBackingArrayIndex(int queueIndex)
        {
            return (FirstIndex + queueIndex) & CapacityMask;
        }

        /// <summary>
        /// 获取队列中给定索引处的元素。
        /// 0获取FirstIndex处的元素。Count-1将获得LastIndex处的元素。
        /// </summary>
        /// <param name="index">从中获取元素的索引。</param>
        /// <return>位于队列中给定索引处的元素。</return>
        public ref T this[int index]
        {
            // TODO：检查内联。
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get
            {
                ValidateIndex(index);
                return ref Span[GetBackingArrayIndex(index)];
            }
        }


        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static int GetCapacityMask(int spanLength)
        {
            return (1 << SpanHelper.GetPowerOf2(spanLength)) - 1;
        }

        /// <summary>
        /// 创建新队列。
        /// </summary>
        /// <param name="initialSpan">开始用作后备内存的范围。</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public QuickQueue(ref Buffer<T> initialSpan)
        {
            Span = initialSpan;
            Count = 0;
            CapacityMask = GetCapacityMask(Span.Length);
            FirstIndex = 0;
            LastIndex = CapacityMask;
            ValidateSpanCapacity(ref initialSpan, CapacityMask);
        }
        /// <summary>
        /// 创建新队列。
        /// </summary>
        /// <param name="pool">要从中拉取跨区的池。</param>
        /// <param name="minumInitialCount">要从池中拉取的区域的最小大小。实际跨度可能更大。</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public QuickQueue(int minimumInitialCount, IUnmanagedMemoryPool pool)
        {
            pool.TakeAtLeast(minimumInitialCount, out Span);
            Count = 0;
            CapacityMask = GetCapacityMask(Span.Length);
            FirstIndex = 0;
            LastIndex = CapacityMask;
            ValidateSpanCapacity(ref Span, CapacityMask);
        }


        /// <summary>
        /// 将队列的后备内存跨度换成新跨度。
        /// 如果新跨度较小,则会截断队列的计数,并丢弃额外的元素。
        /// 旧跨度不会被清除或返回到任何池;如果需要将其池化或清除,则用户必须处理它。
        /// </summary>
        /// <param name="newSpan">要使用的新范围。</param>
        /// <param name="oldSpan">用于元素的上一个范围。</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Resize(ref Buffer<T> newSpan, out Buffer<T> oldSpan)
        {
            Validate();
            Debug.Assert(Span.Length != newSpan.Length, "Resizing without changing the size is pretty peculiar. Is something broken?");
            var oldQueue = this;
            // 截断长度。
            if (oldQueue.Count > newSpan.Length)
                Count = newSpan.Length;
            else
                Count = oldQueue.Count;
            LastIndex = Count - 1;
            FirstIndex = 0;
            CapacityMask = GetCapacityMask(newSpan.Length);
            Span = newSpan;

            oldSpan = oldQueue.Span;

            // 不能保证计数等于Elements.Length,因此必须涵盖这两种情况。
            if (oldQueue.LastIndex >= oldQueue.FirstIndex)
            {
                // 索引是有序的,并且队列中至少有一个元素,因此只需执行一次连续复制。
                oldSpan.CopyTo(oldQueue.FirstIndex, Span, 0, Count);
            }
            else if (Count > 0)
            {
                // 最后一个索引在第一个索引之前,这意味着元素绕过跨度的末端。为每个连续区域复制一份。
                var firstToEndLength = oldSpan.Length - oldQueue.FirstIndex;
                oldSpan.CopyTo(oldQueue.FirstIndex, Span, 0, firstToEndLength);
                oldSpan.CopyTo(0, Span, firstToEndLength, oldQueue.LastIndex + 1);
            }

        }

        /// <summary>
        /// 针对给定大小调整队列的支持数组的大小。
        /// 任何不适合调整大小范围的元素都将被删除,并且计数将被截断。
        /// </summary>
        /// <param name="NewSize">新支持数组中所需的最小元素数。创建的跨度的实际容量可能超过此大小。</param>
        /// <param name="pool">要从中提取新跨度并将旧跨度返回到的池。</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Resize(int newSize, IUnmanagedMemoryPool pool)
        {
            var targetCapacity = pool.GetCapacityForCount<T>(newSize);
            if (targetCapacity != Span.Length)
            {
                var oldQueue = this;
                pool.TakeAtLeast<T>(newSize, out var newSpan);
                Resize(ref newSpan, out var oldSpan);
                oldQueue.Dispose(pool);
            }
        }

        /// <summary>
        /// 将与队列关联的资源返回到池。仍包含在队列中的任何托管引用都将被清除(某些非托管资源也可能被清除)。
        /// </summary>
        /// <param name="pool">用于元素跨度的池。</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Dispose(IUnmanagedMemoryPool pool)
        {
            pool.Return(ref Span);
        }
        /// <summary>
        /// 确保队列有足够的空间容纳指定数量的元素。
        /// </summary>
        /// <param name="count">要保存的元素数。</param>
        /// <param name="pool">要从中提取新跨度并将旧跨度返回到的池。</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void EnsureCapacity(int count, IUnmanagedMemoryPool pool)
        {
            if (count >= CapacityMask)
            {
                Resize(count, pool);
            }
        }

        /// <summary>
        /// 将内部缓冲区压缩到队列中元素数量所需的最小大小。
        /// </summary>
        /// <param name="pool">必要时要从中拉出的池。</param>
        public void Compact(IUnmanagedMemoryPool pool)
        {
            Validate();
            var targetCapacity = pool.GetCapacityForCount<T>(Count);
            if (targetCapacity < Span.Length)
                Resize(targetCapacity, pool);
        }

        /// <summary>
        /// 将元素排队到队列末尾,递增最后一个索引。
        /// </summary>
        /// <param name="element">要入队的项目。</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void EnqueueUnsafely(in T element)
        {
            Validate();
            ValidateUnsafeAdd();
            Span[(LastIndex = ((LastIndex + 1) & CapacityMask))] = element;
            ++Count;
        }

        /// <summary>
        /// 将元素排队到队列的开头,递减第一个索引。
        /// </summary>
        /// <param name="element">要入队的项目。</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void EnqueueFirstUnsafely(in T element)
        {
            Validate();
            ValidateUnsafeAdd();
            Span[(FirstIndex = ((FirstIndex - 1) & CapacityMask))] = element;
            ++Count;
        }
        
        /// <summary>
        /// 将元素排队到队列末尾,递增最后一个索引。
        /// </summary>
        /// <param name="element">要入队的项目。</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Enqueue(in T element, IUnmanagedMemoryPool pool)
        {
            Validate();
            if (Count == Span.Length)
                Resize(Span.Length * 2, pool);
            EnqueueUnsafely(element);
        }

        /// <summary>
        /// 将元素排队到队列的开头,递减第一个索引。
        /// </summary>
        /// <param name="element">要入队的项目。</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void EnqueueFirst(in T element, IUnmanagedMemoryPool pool)
        {
            Validate();
            if (Count == Span.Length)
                Resize(Span.Length * 2, pool);
            EnqueueFirstUnsafely(element);
        }

        /// <summary>
        /// 将一个元素从队列的开头排出队列,使第一个索引递增。
        /// </summary>
        /// <return>元素已从队列中删除。</return>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public T Dequeue()
        {
            Validate();
            if (Count == 0)
                throw new InvalidOperationException("The queue is empty.");
            var element = Span[FirstIndex];
            DeleteFirst();
            return element;

        }

        /// <summary>
        /// 将一个元素从队列末尾排出队列,使最后一个索引递减。
        /// </summary>
        /// <return>元素已从队列中删除。</return>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public T DequeueLast()
        {
            Validate();
            if (Count == 0)
                throw new InvalidOperationException("The queue is empty.");
            var element = Span[LastIndex];
            DeleteLast();
            return element;

        }

        /// <summary>
        /// 尝试从队列的起始处将元素出列,从而递增第一个索引。
        /// </summary>
        /// <param name="element">元素已从队列中删除(如果有)。</param>
        /// <return>如果元素可供删除,则为True,否则为False。</return>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool TryDequeue(out T element)
        {
            Validate();
            if (Count > 0)
            {
                element = Span[FirstIndex];
                DeleteFirst();
                return true;
            }
            element = default;
            return false;

        }

        /// <summary>
        /// 尝试从队列末尾将元素出列,从而递减最后一个索引。
        /// </summary>
        /// <param name="element">元素已从队列中删除(如果有)。</param>
        /// <return>如果元素可供删除,则为True,否则为False。</return>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool TryDequeueLast(out T element)
        {
            Validate();
            if (Count > 0)
            {
                element = Span[LastIndex];
                DeleteLast();
                return true;
            }
            element = default(T);
            return false;

        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void DeleteFirst()
        {
            Span[FirstIndex] = default(T);
            FirstIndex = (FirstIndex + 1) & CapacityMask;
            --Count;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void DeleteLast()
        {
            Span[LastIndex] = default(T);
            LastIndex = (LastIndex - 1) & CapacityMask;
            --Count;
        }

        /// <summary>
        /// 移除给定索引处的元素,同时保留队列的顺序。
        /// </summary>
        /// <param name="queue eIndex">要删除的队列中的索引。该索引使用概念队列,而不是支持数组。</param>
        public void RemoveAt(int queueIndex)
        {
            Validate();
            ValidateIndex(queueIndex);
            var arrayIndex = GetBackingArrayIndex(queueIndex);
            if (LastIndex == arrayIndex)
            {
                DeleteLast();
                return;
            }
            if (FirstIndex == arrayIndex)
            {
                DeleteFirst();
                return;
            }
            // 这是内部问题。

            // 四种可能的情况：
            // 1)队列绕过end且arrayIndex在[0,lastIndex),
            // 2)队列绕过End且arrayIndex在(firstIndex,arrayLength),
            // 3)队列连续且arrayIndex比firstIndex更接近lastIndex,或者
            // 4)队列是连续的,arrayIndex比lastIndex更接近firstIndex
            // 在情况#1和#3中,我们应该将[arrayIndex+1,lastIndex]移动到[arrayIndex,lastIndex-1],删除最后一个元素。
            // 在情况#2和#4中,我们应该将[firstIndex,arrayIndex-1]移动到[firstIndex+1,arrayIndex],删除第一个元素。

            if ((FirstIndex > LastIndex && arrayIndex < LastIndex) || // 案例1
                (FirstIndex < LastIndex && (LastIndex - arrayIndex) < (arrayIndex - FirstIndex))) // 个案3
            {
                Span.CopyTo(arrayIndex + 1, Span, arrayIndex, LastIndex - arrayIndex);
                DeleteLast();
            }
            else
            {
                Span.CopyTo(FirstIndex, Span, FirstIndex + 1, arrayIndex - FirstIndex);
                DeleteFirst();
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static void ClearSpan(ref Buffer<T> span, int firstIndex, int lastIndex, int count)
        {
            if (lastIndex >= firstIndex)
            {
                span.Clear(firstIndex, count);
            }
            else if (count > 0)
            {
                span.Clear(firstIndex, span.Length - firstIndex);
                span.Clear(0, lastIndex + 1);
            }
        }

        /// <summary>
        /// 通过将计数设置为零并将支持数组中的所有相关索引显式设置为默认值来清除队列。
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Clear()
        {
            Validate();
            ClearSpan(ref Span, FirstIndex, LastIndex, Count);
            Count = 0;
            FirstIndex = 0;
            LastIndex = CapacityMask;
        }

        /// <summary>
        /// 清除队列,而不更改支持数组中的任何值。如果队列包含引用类型,则使用此选项时要小心。
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void FastClear()
        {
            Count = 0;
            FirstIndex = 0;
            LastIndex = CapacityMask;
        }

        public Enumerator GetEnumerator()
        {
            return new Enumerator(Span, Count, FirstIndex, CapacityMask);
        }

        public struct Enumerator : IEnumerator<T>
        {
            private Buffer<T> span;
            private readonly int count;
            private readonly int firstIndex;
            private readonly int capacityMask;
            private int index;

            public Enumerator(in Buffer<T> span, int count, int firstIndex, int capacityMask)
            {
                this.span = span;
                this.count = count;
                this.firstIndex = firstIndex;
                this.capacityMask = capacityMask;
                index = -1;
            }

            public T Current
            {
                get { return span[(firstIndex + index) & capacityMask]; }
            }

            public void Dispose()
            {
            }

            object System.Collections.IEnumerator.Current
            {
                get { return Current; }
            }

            public bool MoveNext()
            {
                return ++index < count;
            }

            public void Reset()
            {
                index = -1;
            }
        }

        [Conditional("DEBUG")]
        void ValidateIndex(int index)
        {
            Debug.Assert(index >= 0 && index < Count, "Index must be nonnegative and less than the number of elements in the queue.");
        }

        [Conditional("DEBUG")]
        static void ValidateSpanCapacity(ref Buffer<T> span, int capacityMask)
        {
            Debug.Assert((1 << SpanHelper.GetPowerOf2(span.Length)) - 1 == capacityMask,
                "Capacity mask should be the largest power of 2 that fits in the allocated span, minus one. This is necessary for efficient modulo operations.");
        }

        [Conditional("DEBUG")]
        void ValidateUnsafeAdd()
        {
            Debug.Assert(Count <= CapacityMask, "Unsafe adders can only be used if the capacity is guaranteed to hold the new size.");
        }

        [Conditional("DEBUG")]
        private void Validate()
        {
            Debug.Assert(Span.Length > 0, "Any QuickQueue in use should have a nonzero length Span. Was this instance default constructed without further initialization?");
            ValidateSpanCapacity(ref Span, CapacityMask);
        }

    }
}
